package top.datacluster.basic.algorithm.leetcode;

public class SearchRotateArrayLeetCode33 {

    private int findMin(int[] nums){
        int i = 0;
        int j = nums.length - 1;
        if (nums[i] < nums[j]){
            return i;
        }
        int index = 0;
        while (i <= j){
            index = (j + i) / 2;
            if (nums[index] > nums[index + 1]){
                return index + 1;
            }else{
                if (nums[index] < nums[i]){
                    j = index - 1;
                }else{
                    i = index + 1;
                }
            }

        }
        return 0;
    }

    private int bsearch(int i, int j, int[] nums, int target){

        while (i <= j){
            int index = (j + i) / 2;
            if (nums[index] == target){
                return index;
            }else{
                if (nums[index] < target){
                    i = index + 1;
                }else{
                    j = index - 1;
                }
            }

        }
        return -1;
    }

    public int search(int[] nums, int target) {
        if (nums.length == 0){
            return -1;
        }
        if (nums.length == 1 && nums[0] == target){
            return 0;
        }
        if (nums.length == 1 && nums[0] != target){
            return -1;
        }
        if (target < nums[0] && target > nums[nums.length - 1]){
            return -1;
        }
        int index = findMin(nums);
        int i = 0;
        int j = nums.length - 1;
        if (index == 0){
            return bsearch(0, j, nums, target);
        }
        if (target >= nums[i]){
            return bsearch(0, index - 1, nums, target);
        }else{
            return bsearch(index, j, nums, target);
        }

    }




}
